def insertion_sort(L):
    '''插入排序，升序
    相当于将L[i]提起来，再与 "已排序序列" 中的元素(从后向前)依次比较，
    如果L[i]比较小，则将 "已排序序列" 中的元素依次往后挪一个位置
    '''
    n = len(L)
    if n <= 1:
        return

    # 首先，假设第1个元素L[0]是 "已排序序列"，第2个元素L[1]至最后一个元素L[n-1]是 "未排序序列"
    for i in range(1, n):  # 未排序的元素有 n-1 个，所以共需要 n-1 次插入操作。 i 表示 "未排序序列" 的第1个元素的下标，所以 i 从下标 1 开始

        # 将 "未排序序列" 的第1个元素（temp）提起来，再与 "已排序序列" 中的元素（从后向前）依次比较，
        # 如果 temp 小于 "已排序序列" 中的元素，则将 "已排序序列" 中的元素往后挪一位
        # 如果 temp 大于或等于 "已排序序列" 中的元素，则把 temp 插入该元素的后面
        temp = L[i]  # "未排序序列" 的第1个元素
        j = i
        # j >= 1是因为后续j[j-1]，否则下标越界
        while j >= 1 and temp < L[j-1]:  # 如果 "未排序序列" 的第1个元素，小于 "已排序序列" 中的元素L[j]
            L[j] = L[j-1]  # 则将 "已排序序列" 中的元素L[j-1]的值复制给L[j]，相当于L[j-1]向后挪了一个位置。第一次（j = i）时，会覆盖L[i]，所以前面需要用temp先保存它
            j -= 1
        # 如果while条件为False：
        # 1. j < 1，则将 "未排序序列" 的第1个元素赋值给L[1]
        # 2. temp >= L[j-1]，则将 "未排序序列" 的第1个元素 "插入" 到L[j-1]的后面（自己尝试 i=4 时，就知道了）
        L[j] = temp

        '''
        演示，第3次插入的过程：

        i = 3，此时列表为 [26, 54, 93, 17, 77, 31, 44, 55, 20]，"已排序序列" 为[26, 54, 93]，"未排序序列" 为[17, 77, 31, 44, 55, 20]
        temp = L[3]  # 17

        j = i  # j=3
        此时，while条件为True，L[j] = L[j-1]，即L[3] = L[2] = 93，会覆盖之前的17，所以temp变量的作用就是先保留该值
        列表变为 [26, 54, 93, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=2
        此时，while条件为True，L[j] = L[j-1]，即L[2] = L[1] = 54
        列表变为 [26, 54, 54, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=1
        此时，while条件为True，L[j] = L[j-1]，即L[1] = L[0] = 26
        列表变为 [26, 26, 54, 93, 77, 31, 44, 55, 20]

        j -= 1  # j=0
        此时，while条件为False，L[j] = temp，即L[0] = temp = 17
        列表变为 [17, 26, 54, 93, 77, 31, 44, 55, 20]
        至此，已将 "未排序序列" [17, 77, 31, 44, 55, 20] 的第1个元素17插入到 "已排序序列" [26, 54, 93] 的正确位置
        '''


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    insertion_sort(L1)
    print('After: ', L1)

    # Output:
    # Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
    # After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

    '''
    压力测试，timeit.timeit() 如果from __main__ import L，结果好像不对，所以在函数内初始化相同的L：

    from timeit import timeit

    def insertion_sort():
        # import random
        # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
        # L = list(gen)
        L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]

        n = len(L)
        for i in range(1, n):
            temp = L[i]
            j = i
            while j >= 1 and temp < L[j-1]:
                L[j] = L[j-1]
                j -= 1
            L[j] = temp

        return L


    print('Insertion sort function run 1000 times, cost: ', timeit('insertion_sort()', 'from __main__ import insertion_sort', number=1000), 'seconds.')


    # Output:
    # Insertion sort function run 1000 times, cost:  1.140121377 seconds.
    '''
